package com.sh.sort;

import java.util.Arrays;

/**
 * @ClassName RadixSort
 * @Description 基数排序
 * @Author yaoqiang
 * @Date 2020/11/20 14:33
 * @Version 1.0
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        int[] result = radixSort(arr);
        System.out.println(Arrays.toString(result));
    }

    private static int[] radixSort(int[] arr) {
        //1得到最大的数的个数
        int max=arr[0];
        for (int i=0;i<arr.length;i++){
            if (arr[i]>max){
                max=arr[i];
            }
        }
        int maxLength=(max+"").length();
        int[][] bucket=new int[10][arr.length];//定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        int[] bucketElementCount=new int[10];

        for (int i=0,n=1;i<maxLength;i++,n*=10){
            //针对每个元素的对应位进行排序处理，第一个是各位，第二个是十位，第三个是百位
            for (int j=0;j<arr.length;j++){
                //取出每个元素对应位的值
                int digitOfElement=arr[j]/n%10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //按照这个桶的顺序依次取出，放到原来数组
            int index=0;
            //遍历一遍桶，将桶中的数据放到原数组
            for (int k=0;k<bucketElementCount.length;k++){
                //如果桶中有数，我们才放入到原来的数组
                if (bucketElementCount[k]!=0){
                    for (int j=0;j<bucketElementCount[k];j++){
                        arr[index++]=bucket[k][j];
                    }
                }
                bucketElementCount[k]=0;
            }

        }
        return arr;
    }
}
